Definition (regret bound)

Suppose f1,...,fTf_1,...,f_T are convex, G-Lipschitz, and gradients are LL-Lipschitz. Then, after TT steps, the regret is

ϵ=[∑i=1Tfi(𝐱(i))]−[∑i=1Tfi(𝐱∗)]≤RGT\epsilon = \left[\sum_{i=1}^T f_i(\mathbf{x}^{(i)})\right] - \left[\sum_{i=1}^T f_i(\mathbf{x}^*)\right] \leq RG\sqrt{T}

where 𝐱∗=arg⁡min𝐱⁡∑i=1Tfi(𝐱)\mathbf{x}^* = \arg\min_\mathbf{x} \sum_{i=1}^T f_i(\mathbf{x}) is the offline optimum.
Hence average regret overtime is bounded by ϵT≤RGT\frac{\epsilon}{T} \leq \frac{RG}{\sqrt{T}}.

Goes →0\to 0 as T→∞T \to \infty

See also

References:

  1. https://www.cs.princeton.edu/courses/archive/fall18/cos521/Lectures/lec16.pdf